#pragma once
#include<iostream>
using namespace std;
//递归版搜索二叉树
namespace hcc
{
    template<class K>
    struct BSTnode
    {
        K _val;
        BSTnode<K>* _left;
        BSTnode<K>* _right;
        explicit BSTnode(const K& x=K())
            : _val(x)
            , _left(nullptr)
            , _right(nullptr)
        {}
    };
    template<class K>
    class BST
    {
        public:
        typedef BSTnode<K> node;
        BST()
            :_root(nullptr)
        {}
        BST(const BST<K>& d)
        {
            copy(d._root);
        }
        void copy(node* root)
        {
            _root=_copy(root);
        }
        bool _insert(const K& x)
        {
            return insert(_root,x);
        }
        void print()
        {
            printmid(_root);
            cout<<endl;
        }         
        bool _earse(const K& x)
        {
            return earse(_root,x);
        }
        private:
        node* _root;
        node* _copy(node*& root)
        {
            if(root==nullptr)
                return nullptr;
            node* cur=new node(root->_val);
            cur->_left=_copy(root->_left);
            cur->_right=_copy(root->_right);
            return cur;
        }
        bool insert(node*& root,const K& x)
        {
            if(root==nullptr)
            {
                root=new node(x);
                return true;
            }
            if(x<root->_val) 
                return insert(root->_left,x);
            else if(x>root->_val)
                return insert(root->_right,x);
            else
                return false;
        }
        void printmid(const node* root)
        {
            if(root==nullptr)
                return;
            // cout<<root->_val<<"->";
            printmid(root->_left);
            cout<<root->_val<<"->";
            printmid(root->_right);
        }
        bool earse(node*& root,const K& x)
        {
            if(root==nullptr)
                return false;
            if(x<root->_val)
                return earse(root->_left,x);
            else if(x>root->_val)
                return earse(root->_right,x);
            else
            {
                if(root->_left== nullptr)
                {
                    node* del=root;
                    root=root->_right;
                    delete del;
                    del=nullptr;
                    return true;
                }
                else if(root->_right==nullptr)
                {
                    node* del=root;
                    root=root->_left;
                    delete del;
                    del=nullptr;
                    return true;
                }
                else
                {
                    node* min=root->_right;
                    while(min->_left)
                        min=min->_left;
                    std::swap(min->_val,root->_val);
                    return earse(root->_right,x);
                }
            }
        }
    };
}
